#pragma once
#include <stdexcept>

unsigned fib_mod(unsigned long long n, unsigned long long mod)
{
    if (n < 1 || n > (unsigned long long)1e18)
        throw std::runtime_error("Invalid fib number. Value should be in range [1, 10^18]");

    if (mod < 2 || mod > 100000)
        throw std::runtime_error("Invalid mod. Value should be in range [1, 10^5]");

    unsigned long long x11 = 0;
    unsigned long long x12 = 1;
    unsigned long long x21 = 1;
    unsigned long long a22 = 1;

    unsigned long long F0 = 0;
    unsigned long long F1 = 1;

    unsigned long long tmp11 = 0;
    unsigned long long tmp12 = 0;
    unsigned long long tmp21 = 0;
    unsigned long long tmp22 = 0;

    while (n)
    {
        if (n & 1)
        {
            tmp11 = (F0 * x11 + F1 * x21) % mod;
            tmp12 = (F0 * x12 + F1 * a22) % mod;

            F0 = tmp11;
            F1 = tmp12;
        }

        tmp11 = (x11 * x11 + x12 * x21) % mod;
        tmp12 = (x11 * x12 + x12 * a22) % mod;
        tmp21 = (x21 * x11 + a22 * x21) % mod;
        tmp22 = (x21 * x12 + a22 * a22) % mod;

        x11 = tmp11;
        x12 = tmp12;
        x21 = tmp21;
        a22 = tmp22;

        n >>= 1;
    }

    return F0;
}
